Route planning devices (often referred to as Satellite Nav.'s, Portable Navigation Devices (PND's) or similar) together with web sites accessible across the World Wide Web (WWW) such as http://routes.tomtom.com/ are well known and allow a user thereof to plan a route between two points. Such technology may be referred to generically as electronic route planning or just route planning.
Map data (ie electronic maps) for such electronic route planning comes from specialist map vendors such as Tele Atlas NV. When performed on a PND such route planning typically uses position data from a GPS system. However, other applications may allow a user to input his/her location or other point to be considered for routing planning purposes.
Such map data comprises a plurality of roads (and other navigable paths) which can be described as lines—i.e. vectors or road segments (e.g. start point, end point, direction for a road, with an entire road being made up of many hundreds of such segments, each uniquely defined by start point/end point direction parameters). Such vectors connect nodes which represent intersections between vectors and typically represent a junction in the road represented by the vector.
An electronic map is then a set of such road vectors, nodes, data associated with each vector and node (speed limit; travel direction, etc.) plus points of interest (POIs), plus road names, plus other geographic features like park boundaries, river boundaries, etc., all of which are defined in terms of vectors. All map features (e.g. road vectors, POIs etc.) are typically defined in a co-ordinate system that corresponds with or relates to the GPS co-ordinate system, enabling a device's position as determined through a GPS system to be located onto the relevant road shown in an electronic map and for a route, which aims to be optimal minimising a selected cost function, to be planned to a destination.
The data providing such electronic maps can be extensive. It is known for electronic maps to cover areas having in excess of 120,000,000 vectors and an example of such map data would be a map covering the area of Europe and Russia. As such, planning a route using such map data is complex and can be time consuming. Also, it is known that such route planning is a trade-off between accuracy and time.
Prior art which has considered ideas at improving the speed at which routing can occur includes U.S. Pat. No. 6,636,800 which discusses refinements to the A* best-first search strategy suitable for much smaller map sizes such as the highway road network of Western Europe (having roughly 400,000 vectors).